package com.xiongtian.tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author xiongtian
 * @version 1.0
 * @date 2021/4/19 11:31
 */
public class BinaryTreeNoRecursionDemo {
    public static void main(String[] args) {

        Node root = new Node(1);
        Node node1 = new Node(2);
        Node node2 = new Node(3);
        Node node3 = new Node(4);
        Node node4 = new Node(5);
        Node node5 = new Node(6);
        Node node6 = new Node(7);
        Node node7 = new Node(8);

        root.left = node1;
        root.right = node2;
        node1.left = node3;
        node1.right = node4;
        node2.left = node5;
        node2.right = node6;
        node3.left = node7;

        // 前序遍历
        System.out.println("前序遍历：");
        preOrder(root);
        System.out.println("");
        // 中序遍历
        System.out.println("中序遍历：");
        infixOrder(root);
        System.out.println("");
        // 后序遍历
        System.out.println("后序遍历：");
        postOrder(root);
    }

    // 二叉树的先序遍历（非递归）
    public static void preOrder(Node root) {
        List<Node> list = new ArrayList<>();
        Stack<Node> stack = new Stack<>();

        Node node = root;
        while (null != node || !stack.isEmpty()) {

            while (node != null) {
                list.add(node);
                stack.push(node);
                node = node.left;
            }

            node = stack.pop();
            node = node.right;
        }

        for (Node item : list) {
            System.out.printf("%d ", item.id);
        }
    }

    // 二叉树的中续遍历（非递归）
    public static void infixOrder(Node root) {
        List<Node> list = new ArrayList<>();
        Stack<Node> stack = new Stack<>();

        Node node = root;

        while (null != node || !stack.isEmpty()) {
            while (null != node) {
                stack.push(node);
                node = node.left;
            }

            node = stack.pop();
            list.add(node);
            node = node.right;
        }

        for (Node item : list) {
            System.out.printf("%d ", item.id);
        }
    }


    // 二叉树的后续遍历（非递归）
    public static void postOrder(Node root) {
        Stack<Node> src = new Stack<>();
        Stack<Node> res = new Stack<>();

        src.push(root);

        while (!src.isEmpty()) {
            Node node = src.pop();
            res.push(node);
            if (null != node.left) {
                src.push(node.left);
            }
            if (null != node.right) {
                src.push(node.right);
            }
        }

        while (!res.isEmpty()) {
            System.out.printf("%d ", res.pop().id);
        }
    }


}

class Node {
    int id;
    Node left;
    Node right;

    public Node(int id) {
        this.id = id;
    }

    @Override
    public String toString() {
        return "Node{" +
                "id=" + id +
                '}';
    }
}
